package class29_manacher;

public class Manacher {
    public static char[] getManacherStr(String s){
        char[] ans  = new char[s.length()*2+1];
        for(int i=0;i<ans.length;i++){
            if(i%2==0) ans[i]='#';
            else ans[i]=s.charAt(i/2);
        }
        return ans;
    }

    public static String manacher(String s){
        char[] str = getManacherStr(s);
        int[] r = new int[str.length];//半径数组
        int R = -1;//当前最长回文串的右边界+1
        int C = -1;//当前最长回文串的中心
        for(int i=0;i<str.length;i++){
            int i_ = 2*C-i;
            int l_ = i_-(r[i]);
            if(R<=i){ //这里注意是等于，因为R本身是右边界的+1，所以等于他一定是越界的
                r[i]=1;
                int j=0;
                while(i-j>=0 && i+j<str.length && str[i+j]==str[i-j]) j++;//向外扩展
                r[i] = j;
                if(R==-1 || r[i]>r[C]) {//第一个特殊情况注意考虑
                    R=r[i]+i;
                    C=i;
                }
            }
            else{//包括、超出或平齐 前两种情况反正while第一次都完成不了，所以放在一起简洁一些
                    int j = Math.min(r[i_]-1,i_-(C-r[C]));//找到不用遍历的最大半径，r[i_]-1是对称点的半径-1，i_-(C-r[C])是对称点在最大的范围内部的半径
                    while(i-j>=0 && i+j<str.length && str[i+j]==str[i-j]) j++;//向外扩展
                    r[i] = j;//找到半径
                    if(r[i]>r[C]) {//更新
                        R=r[i]+i;
                        C=i;
                    }
            }

        }
        //长度：
        int len = r[C]-1;
        int start = (C-r[C]+1)/2;
        return s.substring(start,start+len); //截出来
    }

    public  static void main(String[] args) {
        String ans = manacher("bacabab");
        int i=0;
    }
}
